/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode5 {
    public String longestPalindrome(String s) {


        return fun1(s);
    }

    /**
     * 这里采用动态规划算法
     *
     * 1.单字符都是回文串
     * 2.按字符长度来匹配，从长度2到长度length的字符串进行遍历
     * 3.在索引[i,j]的范围内， 如果p[i] = p[j] 并且索引[i + 1，j-1]为回文串，则索引[i,j]为回文串
     * 4.这里，我们保存所有的索引对是否为回文串的值，用true或者false表示，可能性集合为P[length][length]
     *
     * @param s
     * @return
     */
    private String fun1(String s){
        int length = s.length();
        if (length < 2){
            return s;
        }

        boolean P[][] = new boolean[length][length];

        //单字符都是回文串
        for (int i = 0; i < length; i++){
            P[i][i] = true;
        }

        int maxLength = 1;
        int begin = 0;

        char[] array = s.toCharArray();


        //从子字符串长度为2开始遍历
        for (int L = 2; L <= length; L++){
            for (int left = 0; left < length; left++){
                int right = left + L - 1;
                if (right >= length){
                    break;
                }
                if (array[left] != array[right]){
                    P[left][right] = false;
                }else {
                    if (L <= 3){
                        P[left][right] = true;

                    }else{
                        P[left][right] = P[left + 1][right - 1];
                    }
                }

                if (P[left][right] && L > maxLength){
                    begin = left;
                    maxLength = L;
                }
            }
        }



        return s.substring(begin, begin+maxLength);
    }

    public String fun2(String s){

        return "";
    }

    public static void main(String[] args) {
        LeetCode5 leetCode5 = new LeetCode5();
        System.out.println(leetCode5.longestPalindrome("aaabbbccdbbbaaa"));
    }
}
